package org.example.myleet.p1345;

import java.util.*;

public class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        if (n == 1) {
            return 0;
        }
        //记录是否访问过
        boolean[] visited = new boolean[n];
        //预处理，索引相同的值
        HashMap<Integer, List<Integer>> indexesMap = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int num = arr[i];
            List<Integer> indexes = indexesMap.computeIfAbsent(num, k -> new LinkedList<>());
            indexes.add(i);
        }
        //BFS用的队列
        Queue<Integer> queue = new LinkedList<>();
        //初始化
        queue.add(0);
        visited[0] = true;
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                int index = queue.poll();
                if (index == n - 2) {
                    //index倒数第二，只要前进一步就到最后一个，说明找到最小步数了
                    return step + 1;
                } else  {
                    //index往右边走一步
                    int right = index + 1;
                    if (!visited[right]) {
                        queue.offer(right);
                        visited[right] = true;
                    }
                }
                if (index > 0) {
                    //index往左边走一步
                    int left = index - 1;
                    if (!visited[left]) {
                        queue.offer(left);
                        visited[left] = true;
                    }
                }
                //index往所有相同的值走一步
                int num = arr[index];
                List<Integer> indexes = indexesMap.remove(num);
                if (null != indexes) {
                    for (int idx : indexes) {
                        if (idx == n - 1) {
                            //从index跳到idx时发现idx是最后一个，说明找到最小步数了
                            return step + 1;
                        }
                        if (!visited[idx]) {
                            queue.offer(idx);
                            visited[idx] = true;
                        }
                    }
                }
            }
            //记录步数
            ++step;
        }
        return -1;
    }
}
